`
https://leetcode.cn/problems/longest-valid-parentheses/
`

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  const n = s.length
  if (n === 0) return 0
  let maxLen = 0
  const dp = new Array(n).fill(0)
  for (let i = 0; i < n; i++) {
    // 只有遇到右括号才能构成一个有效括号字串
    if (s[i] === ')') {
      // 如果上一个是左括号，就可以直接构成一个有效字串，再拼接上之前的最长有效长度
      if (s[i - 1] === '(') {
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2
      }
      // 如果上一个是右括号，就需要找到上一个有效括号的前一个字符是否存在且是左括号可以匹配
      // 如果上一个有效括号的前一个字符是左括号，那么还需要看是否能跟更前面存在的有效字串拼接起来
      else {
        const prevLen = dp[i - 1]
        const start = i - prevLen - 1
        if (start >= 0 && s[start] === '(') {
          dp[i] = prevLen + 2 + (start >= 1 ? dp[start - 1] : 0)
        }
      }
      // 找到新的有效字串，更新最长长度
      maxLen = Math.max(maxLen, dp[i])
    }
  }
  return maxLen
};